COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.require "let.pub" source file
C00020 ENDMK
C⊗;
.require "let.pub" source file;
∂AILDr. Herbert Stoyan↓DDR 806 Dresden↓Togliattistr. 40↓East Germany∞

Dear Dr. Stoyan:

The parents of LISP were Fortran, FLPL (Fortran list processing language), and IPL.  From
IPL I obtained the idea of list structure and from Fortran the idea of an
algebraic language.

The first idea was that of getting at parts of an expression by computing what
are now called selector functions, and this led to the development of CAR and
CDR.  These were included in FLPL which was implemented by Gelernter's group
at IBM to which I was a consultant. The only thing they  contributed to
the ideas of LISP, (but is was important), was the idea that CONS should have as
value a pointer to the list structure it constructs.  I had previously used
conditional expressions in connection with a chess program written in Fortran,
and in the summer of 1958, I wrote a paper LISP function for differentiate of algebraic
expressions.  Actual work on LISP started in the fall of 58 with the hand coding
of some LISP functions in the assembly language of the IBM 704.  These included
the read and print routines and a simple differentiate.  At that time I simplified
the language by having only one CONS a function of two arguments.  Previously,
CONS had 4 arguments because the machine word of the IBM 704 had 4 parts that
could be used.  Another important development at that time was to use a garbage collector
in order to hide the erasing of list structures from the user.  

When I started
to write my paper for the Communications of the ACM in 1959, I wrote the EVAL
function as an analog to the universal Turing machine in order to show that
LISP was a suitable basis for recursive function theory.  The S-expression
form of LISP
was invented in this manner, and perhaps some other simplifications were made
at that time in order to clarify the  logical structure.  

Up to that time, we intended to write a compiler for an
M-expression version of LISP, but this was going slowly, so
Steve Russell initiated hand coding
of the EVAL function of my paper - using it as an interpreter for LISP.

The first version of LISP was finished in late 1959 and a second version, 
LISP 1.5 was finished in about 1961 and is described in the LISP 1.5 Programmer's
manual published by MIT press.

Let me now deal explicitly with your questions.

	1.  LISP was the only language that I followed to implementation.  But I have
occasionally thought about and written memoranda about general purpose languages.
My main contribution to ALGOL was the idea of conditional expressions, but
the syntax for conditional expression in ALGOL was proposed by John Backus in a
committee meeting.

 	2. I agree with you that the S-expression notation is one of the key ideas, and as I
explained before, I initially did it, because I wanted to make my
paper mathematically clean. Only then did the advantages
of using the same higher level form for program and data become apparent.

	3. In my opinion, the language was never finished, in that the PROG feature,
the psuedo functions that modify list structure, and the call-by-value 
structures of EVAL are made anomalous and sub-optimal.  I hope
to return to these subjects.  The interpreter was originally a stop-gap and even
though it is now easy to write compilers, most LISP systems have an interpreter and
a compiler.

	4.  Besides me, there were about 3 young professional programmers and several
graduate students involved in the implementation of the first versions of LISP
Besides writing the interpreter, Steven Russell also played an important part in
inventing the FUNARG device that solved a difficult problem
concerning free variables in functions that are given to functions as arguments.

This problem later came up in connection with ALGOL and I was surprised that
we already had a better solution than most of the ALGOL compiler writers.  I
don't know exactly who invented the FUNARG device, but I am sure I didn't.

The atmosphere of the MIT-AI project was very informal at first, partly
because the project had a rather informal existence.  There was no written
proposal for its establishment and all the people were supported by the MIT
Computation Center and the MIT Research Lab of Electronics.  The only supporting
project people were the secretary and the programmers, and our only equipment
was a keypunch.  People who lost interest in the project simply switched to
another activity.

	5.  The idea that there should be a PROG feature was present from the beginning.
The surprise was that so much could be done without using it.  However, I
don't remember who actually devised the notation used for PROG.  It certainly
didn't get much thought, but the explicit RETURN was better than the ALGOL
scheme.

	6.  The first big user of LISP was James Slagle, then a graduate student writing
a dissertation on symbolic integration.  Much effort was put into solving the
problems that arose in his work.

	7.  The first reaction to LISP by other implementers was to invent their own
languages taking some LISP features.  However, LISP was actually copied for
other machines than the IBM 704 in the early 60's, certainly by 1963 but probably
earlier.  Most of the early implementers had no real user community and not
much was done with the language after their implementation.

	8.  Harold MacIntosh implemented LISP in Mexico in the early 60's, but I
don't know when LISP was first used in Europe.  Certainly, the major
implementation of LISP for the IBM 360 was in use in Europe by 1969.

	9.  Since 1964, many versions of LISP have been written.  The most notable were
BBNLISP which is now called INTERLISP, which was optimized for a paged
machine.  The main person involved in this is Warren Teitelman, now at
Xerox Palo Alto Research Center.  In my opinion, much of what has
been done is excessive elaboration; the INTERLISP manual is very long.  However,
many of the debugging features of INTERLISP are very useful.  Some
very interesting work is also being done by Prof. Goto of Tokyo University
in eliminating duplicate list structure.  The discovery by
Vuillemin and Cadiou at Stanford that the LISP EVAL does not always give
the least defined solution of the functional equation was a surprise to
me, and recent work on "lazy evaluators" that delay evaluation as long
as possible by James Morris at Xerox, among other people, is also
interesting, and I am hopeful that something along these lines can be included
in a practical version of LISP.

	10.  I wrote a LISP interpreter in Ershov's language ALPHA for the BESM-6 in
December 68.  I left before I had time to debug it, but I think  somone
in Novosibirsk finished it.  My LISP interpreter was basically a programming
exercise because the BESM-6 has too little memory for interesting LISP
programs.  I have also heard that Lavrov wrote a LISP for the BESM-6, but
his version was independent of mine.

	11.  As you see from the above, the design process of LISP was not entirely
straightforward, in that there did not exist a single unified plan before
getting started, and the goals changed during the project.  The goal about
making the system mathematically clean, contributed to the practical 
utility of LISP and to its long life.  It is now almost 18 years old and there is
no obvious candidate for replacing it.  I am thinking about holding a 20th
anniversary celebration in Sept 1978 together with a conference concerned with
how to do the whole thing better - both from theoretical and practical points
of view.

Enclosed also is a copy of the speech.  I was reluctant to send it to you
because I think it has some mistakes in substance as well as typographical
errors.  Moreover, I have not taken the time to consult with anyone
else concerning exactly who did what in the late 50's and early 60's.

I will refer your questions about MLISP2 to David Smith who is still in
the area.

If you are interested in trying to come to the 20th anniversary conference in
1978, I will try to keep you informed.

Here are some answers to your questions of February:

	1. At the end of 1958, some paper programs had been written, and
some of them had been hand-translated for the IBM 704.

	2. I will try to get you a copy of that manual, but it may not
be easy.

	3. We already knew that we wanted to write LISP 2.

	4. The acronyms %2car%1 and %2cdr%1 are my invention in 1956.
The name %2cons%1 and what it does as program are also mine.  Their
invention is that its value should be a pointer to the list structure
it constructs.

	5. Explained in beginning of the letter.

	6. Everything that I can think of that is in LISP was done
before I had the opportunity to influence ALGOL.  I was not on the
ALGOL 58 international committee, and maybe my work on LISP won me
a place on the 1960 committee.

	7. LISP I was the 704-LISP.  If you want, I could try to
determine if listings of the interpreter still exist.

	8. Brayton is at Thomas J. Watson Laboratory, IBM Corporation,
Yorktown Heights, New York.

	9. There were minor differences at least in that the implemented
version allowed for numbers and provided specially for NIL and T so they
didn't have to be quoted.  I don't remember %2appq%*.  While I intended
to allow some combinators in order to get more ways of forming functions,
this wasn't implemented, and LAMBDA, LABEL, and atoms were all.  Of
course LABEL was hardly ever used.
Correction: Any LISP expression could appear in functional position, and
it would be evaluated.  I forgot, because this is logically anomalous,
and I discouraged its use.  I believe some people used it, however.

	I assume that by functional indicators, you mean FUNCTION.
The use of FUNCTION instead of QUOTE served a purpose in 704 LISP,
but I forget what.  Later LISPs have simplified the treatment
of functions with functions as arguments to the detriment of correctness
in order to get programs that run faster.  The a-list was a list of
dotted pairs.

	10. LISP 1.5 was a successor to LISP I on the same machine.
The new name came with the new manual.  It was called LISP 1.5, because
ideas for LISP 2 were already being developed.  A LISP 2 project
was started at Systems Development Corporation in the early 1960s,
and a system was written and debugged for the Q-32 computer.  This
was a military computer, and only the one at SDC was used for
scientific work.  The machine had 48K of memory of 48 bit words, and
in principle was a better machine than the IBM 7090.  Unfortunately,
it never got any more memory and was to expensive to maintain.
A project to transfer LISP 2 from the SDC machine to the IBM 360 and
the Digital Equipment Corporation PDP-6 computer was started but
never completed.  Many memoranda on LISP 2 exist.

	11. Already answered.

	12. I went to Stanford in September 1962.

	13. Jan Kent's address in the 1972 ACM directory is
Nils Juelgst 39B, Oslo 2, Norway.  If that doesn't work I would
suggest writing to him c/o IBM Corporation, Oslo Norway.

.sgn